
public class Leetcode213 {
    public static void main(String[] args) {

        System.out.println(rob(new int[]{1, 2, 3, 1}));
    }

    public static int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }

    public static int rob(int[] nums, int start, int end) {
        if (end - start + 1 == 1) {
            return nums[start];
        }

        if (end - start + 1 == 2) {
            return Math.max(nums[start], nums[start + 1]);
        }

        int[] currentIndexMax = new int[end - start + 1];

        currentIndexMax[0] = nums[start];
        currentIndexMax[1] = Math.max(nums[start], nums[start + 1]);
        for (int i = 2, j = start + 2; i < end - start + 1; i++, j++) {
            currentIndexMax[i] = Math.max(currentIndexMax[i - 1], currentIndexMax[i - 2] + nums[j]);
        }

        return currentIndexMax[end - start];
    }

}

